package com.aqie.easy.bucket;

/**
 * 697 数组的度
 */
public class FindShortestSubArray {
    /**
     * 1. todo 9ms
     * @param nums
     * @return
     */
    public int findShortestSubArray(int[] nums) {
        if (nums.length == 1) return 1;

        int min = nums[0], max = nums[0];
        for (int num : nums) {
            if (num > max) max = num;
            if (num < min) min = num;
        }

        int len = max - min + 1;
        int[] count = new int[len]; // 记录每个数的个数
        int[] span = new int[len]; // 最大跨度
        int[] firstPos = new int[len]; // 第一次出现的位置

        for (int i = 1; i <= nums.length; i++) {
            // 从1开始, 避免从0开始
            int index = nums[i - 1] - min;
            count[index]++;
            if (firstPos[index] == 0) {
                span[index] = 1; // 跨度至少为1(1个数)
                firstPos[index] = i;
            } else {
                span[index] = i - firstPos[index] + 1;
            }
        }

        int topFreq = 0;  // 出现的最大频数
        for (int c : count)
            topFreq = Math.max(topFreq, c);

        if (topFreq == 1) return 1;

        int res = nums.length;
        for (int i = 0; i < count.length; i++) {
            if (count[i] == topFreq) {
                // 找出出现频率最高的数, 取最小跨度
                res = Math.min(res, span[i]);
            }
        }
        return res;


    }

    /**
     * 2, 桶计数 5ms
     * @param nums
     * @return
     */
    public int findShortestSubArray2(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        // 找到数组中的最大元素值
        int max = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max)
                max = nums[i];
        }
        //创建max + 1个桶
        int[] counts = new int[max + 1];//存储数组元素出现次数
        int[] fidx = new int[max + 1];//存储元素起始下标
        int[] lidx = new int[max + 1];//存储元素最后下标

        for (int i = 0; i < nums.length; i++) {
            if (counts[nums[i]] == 0) {
                fidx[nums[i]] = i;
            }
            counts[nums[i]]++;
            lidx[nums[i]] = i;
        }

        //查找元素出现次数最多(count[i]最大)，且长度最短（lidx[i] - fidx[i]最小）的长度
        int minSubIdx = Integer.MAX_VALUE;
        int maxCount = 0;
        for (int i = 0; i < counts.length; i++) {
            int subIdx = lidx[i] - fidx[i];
            if (counts[i] > maxCount) {
                maxCount = counts[i];
                minSubIdx = subIdx;
            } else if (counts[i] == maxCount && subIdx < minSubIdx){
                minSubIdx = subIdx;
            }
        }

        return minSubIdx + 1;
    }


    public static void main(String[] args) {
        int[] arr = {1,5,0,3,0,8,7,9,0,3,7};
    }
}
